package com.springchang.algorithm.prim;

import java.util.Arrays;

/**
 * 普里姆算法解决图中最小路劲总和问题
 * @author 张翠山
 * @date   20211004
 */
public class PrimAlgorithm {

    public static final int INF = 10000;

    public static void main(String[] args) {

        //顶点数据
        char[] vertex = new char[]{'A', 'B', 'C', 'D', 'E', 'F', 'G'};

        //边的领接矩阵
        int[][] edges = new int[][]{
                {INF, 5, 7, INF, INF, INF, 2},   //A
                {5, INF, INF, 9, INF, INF, 3},   //B
                {7, INF, INF, INF, 8, INF, INF}, //C
                {INF, 9, INF, INF, INF, 4, INF}, //D
                {INF, INF, 8, INF, INF, 5, 4},   //E
                {INF, INF, INF, 4, 5, INF, 6},   //F
                {2, 3, INF, INF, 4, 6, INF}      //G
        };


        //创建一个Graph对象
        MGraph mGraph = new MGraph(vertex.length);

        //初始化图的数据
        mGraph.initData(vertex, edges);

        //打印图的数据
        mGraph.printGraph();

        //调用prim算法
        mGraph.prim(0);
    }


    /**
     * 带权图抽象数据结构
     */
    private static class MGraph {
        private int size; //图的节点个数

        private char[] vertex; //图的地点数组

        private int[][] edges; //邻接矩阵，记录边的权值

        //默认构造函数
        public MGraph() {
            //默认边节点为16个
            size = 16;
            vertex = new char[size];
            edges = new int[size][size];
        }

        public MGraph(int size) {
            this.size = size;
            vertex = new char[size];
            edges = new int[size][size];
        }

        public void initData(char[] vertex, int[][] edges) {
            this.vertex = vertex;
            this.edges = edges;
        }

        //打印图的数据
        public void printGraph() {
            for (int[] edge : edges) {
                System.out.println( Arrays.toString(edge));
            }
        }

        /**
         * 普利姆算法实现
         * @param startVertex 开始遍历下标
         */
        public void prim(int startVertex) {

            //visited数组记录下标为i的顶点是否被访问过
            boolean[] visited = new boolean[size];

            //先访问起始点 startVertex
            visited[startVertex] = true;

            //最大权值
            int maxWeight = INF;
            //记录边的起始节点
            int souce = -1;
            //记录变的结束节点
            int target = -1;

            //寻找边：一个有size个地点的图，最少有size-1条边，所以遍历循环size-1遍
            for (int k = 1; k < size; k++) {
                //遍历到节点i，两层循环目的是为了找到k当前值的最优路劲
                for (int i = 0; i < size; i++) {
                    //遍历整个图的边，找到最优解
                    for (int j = 0; j < size; j++) {
                        if(visited[i] && !visited[j] && edges[i][j] < INF && edges[i][j] < maxWeight) {
                            maxWeight = edges[i][j];
                            souce = i;
                            target = j;
                        }
                    }
                }

                //输出当前最优解
                System.out.println("第"+k+"步，找到当前最优解:<"+vertex[souce]+","+vertex[target]+">,权值:"+maxWeight);

                //两层遍历结束，已经找到了当前第i条边的最优解，则做扫尾工作
                maxWeight = INF;
                //标记刚找打的节点为已经被访问过
                visited[target] = true;
            }
        }
    }
}
